Maps have been created and used by mankind for thousands of years. They facilitate travel, logistics, planning, defining the boundaries of property rights, and the like. Cartography has changed dramatically because of advances in technology. The traditional tools of cartography such as the telescope, the sextant, and the compass are being replaced by digital photography, GPS surveying and computer databases. In addition to better surveying technologies, map presentation technology has changed dramatically as well. Traditional maps that were simply hand-drawings on paper are rapidly being replaced by computer displays that can provide dynamic information tailored to a specific user.
In addition, fixed maps, e.g. maps that have a fixed view and fixed information, are being replaced by dynamic maps where a user can select a specific view and customize the information that is displayed. Furthermore, searching functionality is common in many computer-based maps. A user of computer-based maps can usually select a position and conduct a search for specific information. That information may then be represented on the user's customized map, creating a representation that is tailored to the user's request(s).
Oftentimes the information sought out by a user may be information associated with a position or object rather than a physical characteristic. For example, one common use of interactive maps is to allow a user to search for a specific kind of business. For example a user may search for all businesses that sell pizza within a certain distance from a specific location. The results to such a search can yield a computer-implemented map that displays markers indicating all the pizza parlors in the relevant area. Moreover, in addition to the advances in interactive mapping, location-based information-gathering technologies have advanced rapidly as well. For instance, modern demographic techniques have arisen to determine very detailed information about locations, persons, businesses, etc. Furthermore, satellite images for every region of the earth have been obtained, and several conventional systems that utilize satellite (or other orthographic-style) imagery in connection with street-side imagery are in being developed and enhanced. The demands for these and other location-based information will continue to increase as more advances are made in the relevant fields.
However, with the increased availability of location-based information, it is becoming increasingly important for a mapping and/or location-based query system to provide efficient storage and retrieval mechanisms to reduce the resources required to operate the system. The combination of the aforementioned difficulties has resulted in inefficient mechanisms for facilitating location-based searching. No effective technology has previously been developed to adequately resolve the current difficulties related to location-based searching.
For example, there are inefficiencies in the prior art with regard to processing relevant information within a data store. Typically, a data store of location-related information utilizes two kinds of inverted indices, one for keywords and another for the location. The first inverted index can be implemented as a 2-dimensional array where the first column is an array of keywords and the second column is associated with a set of documents that contain that keyword. The second inverted index is also sometimes implemented as a 2-dimensional array in the prior art, where the first column is a location and the second column is a set of documents associated with the position indicated in the first column. When a user performs a search, there are generally at least three criteria associated with the search (1) the location to be searched; (2) the keyword to search; and (3) limiting criteria.
The limiting criteria can be, e.g. a radius limit that extends from the location to an arbitrary distance. Additionally or alternatively the limiting criteria can be a limit on the number of results returned such as returning the 100 closest results. Generally, the first inverted index is searched in which a set, S1, of documents are made that match the keyword. Next, some conventional systems perform a second search on the second inverted index. The search looks to the first column to determine how close that location is to the location is in the search string. If the limiting criteria are satisfied, the set is included in set S2. The computer continues to search and all sets that are returned are returned are added to S2. When the search of the second inverted index is finished the set S2 is complete. Now the two sets must be intersected. The results are the intersection of S1 and S2, (S1∩S2). The aforementioned processed is a join operation (e.g., an inner join) for joining two inverted indices. This process is extremely expensive in terms of system resources and, as such, often referred to as the “join problem” because of the inefficiencies associated with this process.
In addition to the join problem, other difficulties exist. For example, many conventional systems rely exclusively on “back-end” evaluation of location-based queries. Back-end access typically involves disk reads, which can be orders of magnitude slower than accessing data in a cache. Implementing a system with a front-end cache is a common strategy in the prior art to increase efficiency in some fields. However, traditional caching schemes have failed to adequately employ caches for location-based queries because it is very rare for a search to be carried out from exactly the same location and with exactly the same keyword.
Generally, a location-based search involves two or three parameters. They are conducted as a search of a keyword from a certain location. There are no known strategies to determine if cached results are sufficient for a subsequent search made from a nearby location rather than from an exact location. This occurs because data in a cache is usually constructed based upon a previous search, such as the one described above, that goes to the back-end and joins two inverted indices. Hence, the data in the cache will be based upon a key that contains both keyword and location information. Thus, in order to retrieve a record (from either the back-end or the cache) the key must match exactly in both dimensions, which makes cached results of little value in conventional systems.
Therefore, what is needed is a solution that can remedy both the join problem and, as well, make use of a cache for storing location-based results in a manner that can be employed for subsequent queries, even when the location is not an exact match.